/*
https://leetcode.cn/problems/best-position-for-a-service-centre/solutions/339163/fu-wu-zhong-xin-de-zui-jia-wei-zhi-by-leetcode-sol/
 */
public class Solution1515 {
    public double getMinDistSum(int[][] positions) {
        double eps=1e-12,alpha=1,decay=1e-3;
        double x=0,y=0;
        for (int[] position : positions) {
            x+=position[0];
            y+=position[1];
        }
        x/=positions.length;
        y/=positions.length;
        while (true){
            double xPrev=x,yPrev=y,dx=0,dy=0;
            for (int[] position : positions) {
                dx += (x - position[0]) / (Math.sqrt((x - position[0]) * (x - position[0]) + (y - position[1]) * (y - position[1]) + eps));
                dy += (y - position[1]) / (Math.sqrt((x - position[0]) * (x - position[0]) + (y - position[1]) * (y - position[1]) + eps));
            }
            x-=alpha*dx;
            y-=alpha*dy;
            alpha*=(1.0-decay);
            if (Math.sqrt((x-xPrev)*(x-xPrev)+(y-yPrev)*(y-yPrev))<eps){
                break;
            }
        }
        double ans=0;
        for (int[] position : positions) {
            ans+=Math.sqrt((x-position[0])*(x-position[0])+(y-position[1])*(y-position[1]));
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1515().getMinDistSum(new int[][]{{0,1},{1,0},{1,2},{2,1}}));
    }
}
